package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Greedy;

import java.util.*;

/**
 * TODO 好难啊
 * step = 1
 * A 4
 * B 3
 * C 2
 *
 * @author tzp
 * @since 2020/10/17
 */
public class LC621_2 implements Greedy {
    public int leastInterval(char[] tasks, int n) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int c : tasks) {
            counts.compute(c, (key, oldValue) -> oldValue == null ? 1 : oldValue + 1);
        }
        List<Integer> cnts = new ArrayList<>(counts.values());

        int totalTime = 0;
        int curRemoves = 0;
        while (cnts.size() > 0) {
            cnts.sort(Comparator.reverseOrder());
            curRemoves = Math.min(cnts.size(), n + 1);
            int removed = 0;
            for (int i = 0; i < curRemoves; i++) {
                int remained = cnts.get(i + removed) - 1;
                if (remained == 0) {
                    cnts.remove(i + removed);
                    removed--;
                } else {
                    cnts.set(i + removed, remained);
                }
            }
            totalTime += n + 1;
        }
        if (curRemoves != n + 1) {
            totalTime = totalTime - (n + 1) + curRemoves;
        }
        return totalTime;
    }

    public static void main(String[] args) {
        System.out.println(new LC621_2().leastInterval(new char[]{
                'A', 'A', 'A', 'B', 'B', 'B'}, 2));//8
        System.out.println(new LC621_2().leastInterval(new char[]{
                'A', 'B', 'C', 'D', 'E', 'A', 'B', 'C', 'D', 'E'}, 4));//10
        System.out.println(new LC621_2().leastInterval(new char[]{
                'A', 'A', 'A', 'B', 'B', 'B', 'C', 'C', 'C', 'D', 'D', 'E'}, 2));//12
        System.out.println(new LC621_2().leastInterval(new char[]{
                'A', 'A', 'A', 'A', 'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G'}, 2));//16

        //FIXME 又来一种思路??? 尽量让idle的地方最少没错, 但是也不能浪费.
        // 6 1 1 1 1 |2
        // 3 3 3 2 1 |2
        // 3 3 |2
        // 应该结合这两个代码中的思想, 形成第三版:
        // 3 3 3 2 1
        // ABC ABC ABC DE_D 错误解, 其实一组一组考虑,前两组是ok的
        // 到ABC DE_D这里, D是频次最高的, 应该先安排D了
    }
}
